#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct BinearyTreeNode {
    int key;
    struct BinearyTreeNode *pLeft;
    struct BinearyTreeNode *pRight;
} BinearyTreeNode;

void CreateBinearyTree(BinearyTreeNode **pNode, int *arr, int index, int length) {
    if (!arr || index >= length || index < 0 || arr[index] == 0) {
        free(*pNode);
        *pNode = NULL;
        return;
    }

    BinearyTreeNode *pLeft = (BinearyTreeNode *) malloc (sizeof(BinearyTreeNode));
    BinearyTreeNode *pRight = (BinearyTreeNode *) malloc (sizeof(BinearyTreeNode));
    CreateBinearyTree(&pLeft, arr, 2 * index + 1, length);
    CreateBinearyTree(&pRight, arr, 2 * index + 2, length);

    (*pNode)->key = arr[index];
    (*pNode)->pLeft = pLeft;
    (*pNode)->pRight = pRight;
}

void PrintArray(int *arr, int length) {
    if (!arr) {
        return;
    }

    int i;
    for (i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void VisitNode(BinearyTreeNode *pNode) {
    if (pNode) {
        printf("%d ", pNode->key);
    }
}

void BinearyTreePreOrder(BinearyTreeNode *pRoot) {
    if (!pRoot) {
        return;
    }

    VisitNode(pRoot);
    BinearyTreePreOrder(pRoot->pLeft);
    BinearyTreePreOrder(pRoot->pRight);
}

void BinearyTreeMidOrder(BinearyTreeNode *pRoot) {
    if (!pRoot) {
        return;
    }

    BinearyTreeMidOrder(pRoot->pLeft);
    VisitNode(pRoot);
    BinearyTreeMidOrder(pRoot->pRight);
}

void BinearyTreeAfterOrder(BinearyTreeNode *pRoot) {
    if (!pRoot) {
        return;
    }

    BinearyTreeAfterOrder(pRoot->pLeft);
    BinearyTreeAfterOrder(pRoot->pRight);
    VisitNode(pRoot);
}

void ConvertToListCore(BinearyTreeNode *pNode, BinearyTreeNode **pLastNodeInList) {
    if (!pNode) {
        return;
    }

    BinearyTreeNode *pCurrent = pNode;
    if (pNode->pLeft != NULL) {
        ConvertToListCore(pCurrent->pLeft, pLastNodeInList);
    }

    pCurrent->pLeft = *pLastNodeInList;
    if (*pLastNodeInList != NULL) {
        (*pLastNodeInList)->pRight = pCurrent;
    }

    *pLastNodeInList = pCurrent;

    if (pCurrent->pRight != NULL) {
        ConvertToListCore(pCurrent->pRight, pLastNodeInList);
    }
}

BinearyTreeNode* ConvertToList(BinearyTreeNode *pRoot) {
    BinearyTreeNode *pLastNodeInList = NULL;
    ConvertToListCore(pRoot, &pLastNodeInList);

    BinearyTreeNode *pHeadList = pLastNodeInList;
    while (pHeadList != NULL && pHeadList->pLeft != NULL) {
        pHeadList = pHeadList->pLeft;
    }
    return pHeadList;
}

int main() {
    int length = 16;
    int *arr = (int *) malloc (sizeof(int));
    int i;
    srand(time(NULL));
    for (i = 0; i < length; i++) {
        arr[i] = rand() % 100;
    }
    PrintArray(arr, length);

    BinearyTreeNode *pRoot = (BinearyTreeNode *) malloc (sizeof(BinearyTreeNode));
    CreateBinearyTree(&pRoot, arr, 0, length);
    BinearyTreePreOrder(pRoot);
    printf("\n");
    BinearyTreeMidOrder(pRoot);
    printf("\n");
    BinearyTreeAfterOrder(pRoot);
    printf("\n");

    BinearyTreeNode *list = ConvertToList(pRoot);
    while (list->pRight != NULL) {
        printf("%d ", list->pRight->key);
        list = list->pRight;
    }
    printf("\n");

    return 0;
}
